package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC78 {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (null == nums || nums.length <= 0) {
            return res;
        }
        List<Integer> curRes = new ArrayList<>();
        for (int i = 1; i <= nums.length; i++) {//i indicates step
            subsetsDFS(nums, 0, i, res, curRes);
        }

        res.add(new ArrayList<>());
        return res;
    }

    public void subsetsDFS(int[] nums, int start, int reqSize,
                           List<List<Integer>> res, List<Integer> curRes) {
        if (curRes.size() == reqSize) {
            res.add(copyList(curRes));
            return;
        }

        if (start >= nums.length) {
            return;
        }

        for (int j = start; j < nums.length; j++) {
            curRes.add(nums[j]);
            subsetsDFS(nums, j + 1, reqSize, res, curRes);
            curRes.remove(curRes.size() - 1);
        }
    }


    public List<Integer> copyList(List<Integer> ori) {
        List<Integer> copy = new ArrayList<>();
        for (int i : ori) {
            copy.add(i);
        }
        return copy;
    }


    public static void main(String[] args) {
        LC78 an = new LC78();
        int[] arr = {1, 2, 3};
        System.out.println(an.subsets(arr));
    }
}
